package org.simtube.util;

import java.util.Random;

import org.simtube.index.CEntry;
import org.simtube.index.Region;

/**
 * OrderedEntryQueue is a priority queue to store the k-NN search results, these
 * entries are ordered by its distance to the query region
 * 
 * @author Li Yujia
 *
 */
public class OrderedEntryQueue {
	
	private CEntry[] e;
	private int capacity;
	private int size;
	private MaxEntryComparator comp;
	private Region q;
	
	public OrderedEntryQueue(int cap, Region q) {
		comp = new MaxEntryComparator(q);
		this.q = q;
		e = new CEntry[cap];
		capacity = cap;
		size = 0;
	}
	
	/**
	 * Insert an entry into the queue
	 * @param en The CEntry to be inserted
	 * @return True if the entry is inserted, false otherwise
	 */
	public boolean insert(CEntry en) {
		
		if(size == capacity && comp.compare(e[size - 1], en) < 0)
			return false;
		
		int p = size;
		while(p > 0 && comp.compare(e[p - 1], en) > 0) {
			if(p < capacity)
				e[p] = e[p - 1];
			p--;
		}
		
		e[p] = en;
		
		size = (size < capacity ? (size + 1) : size);
		
		return true;
	}
	
	/**
	 * Return the maximum distance from elements in the queue to the query
	 * region q.
	 * 
	 * @return The maximum distance
	 */
	public double maxDistance() {
		return (size > 0 ? Region.distance(e[size - 1].getRegion(), q) : 0);
	}
	
	/**
	 * Clean the queue, the size will be zero after cleaning
	 */
	public void clear() {
		size = 0;
	}
	
	/**
	 * Reset the query region q
	 * 
	 * @param q The query region
	 */
	public void setQRetion(Region q) {
		this.q = q;
	}
	
	public void printQueue() {
		for(int i = 0; i < size; i++) {
			System.out.println((i + 1) + " " + e[i].getRegion() + ", "
					+ Region.distance(e[i].getRegion(), q));
		}
		System.out.println("Max distance: " + maxDistance());
	}
	
	public int size() {
		return size;
	}
	
	public boolean isFull() {
		return (size == capacity);
	}
	
	public CEntry[] toArray() {
		return e.clone();
	}
	
	public static void main(String[] args) {
		double[] dv = new double[2];
		dv[0] = 1;
		dv[1] = 0;
		
		Random r = new Random();
		Region reg = new Region(new DocVector(dv), 0);
		OrderedEntryQueue q = new OrderedEntryQueue(5, reg);
		for(int i = 0; i < 20; i++) {
			dv = new double[2];
			dv[0] = r.nextDouble();
			dv[1] = r.nextDouble();
			
			Region nr = new Region(new DocVector(dv), 0);
			
			System.out.println((i + 1) + " " + nr + ", " + Region.distance(reg, nr));
			
			CEntry en = new CEntry(nr, i + 1);
			q.insert(en);
			
			q.printQueue();
		}
	}
}
